#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL maxn=100000000;
LL primeNums[maxn],prime_cnt=0;
bitset<maxn> is_prime;
bool isPrime(LL n)
{
    bool res=true;
    if (n<=1)
    {
        res=false;
    }
    else
    {
        LL upper=(LL)(sqrt(1.0*n));
        for (LL i=2;i<=upper ;++i )
        {
            if (n%i==0)
            {
                res=false;
                break;
            }
        }
    }
    return res;
}
void prime_table(LL n)
{
    for (LL i=2;i<=n ;++i )
    {
        if (isPrime(i))
        {
            primeNums[++prime_cnt]=i;
            is_prime[i]=1;
        }
    }
}
void eulurSeive(LL n)
{
    is_prime.set();
    is_prime[0]=0,is_prime[1]=0;
    for (LL i=2;i<=n ;++i )
    {
        if (is_prime[i])
        {
            primeNums[++prime_cnt]=i;
        }
        for (LL j=1;j<=prime_cnt&&i*primeNums[j]<=n ;++j )
        {
            is_prime[i*primeNums[j]]=0;
            if (i%primeNums[j]==0)
            {
                break;
            }
        }
    }
}
void eratosthenesSeive(LL n)
{
    is_prime.set();
    is_prime[0]=0,is_prime[1]=0;
    for (LL i=2;i<=n ;++i )
    {
        if (is_prime[i])
        {
            primeNums[++prime_cnt]=i;
            for (LL j=2*i;j<=n ;j+=i )
            {
                is_prime[j]=0;
            }
        }
    }
}
int main_119()
{
//    prime_table(10000000);//13.045+13.085+13.016
//    eulurSeive(10000000);//0.560+0.565+0.569
//    eratosthenesSeive(10000000);//0.765+0.760+0.753
//    printf("%lld",primeNums[prime_cnt]);
    return 0;
}
